using Nito.Collections;
using SharpGraphT.Sharp.Sharp.Util;

namespace SharpGraphT.Traverse;

public class BreadthFirstIterator<TV, TE> : CrossComponentIterator<TV, TE,
    BreadthFirstIterator<TV, TE>.SearchNodeData> where TE : class, new() {
    private Deque<TV> _queue = new();

    public BreadthFirstIterator(IGraph<TV, TE> g) : this(g, null) { }

    public BreadthFirstIterator(IGraph<TV, TE> g, TV startVertex) : base(g,
        startVertex) { }

    public BreadthFirstIterator(IGraph<TV, TE> g, IEnumerable<TV> startVertices)
        : base(g, startVertices) { }

    protected override bool IsConnectedComponentExhausted() => !_queue.Any();

    protected override void EncounterVertex(TV vertex, TE edge) {
        var depth = edge == null
            ? 0
            : GetSeenData(graph.GetOppositeVertex(edge, vertex)).Depth + 1;
        PutSeenData(vertex, new SearchNodeData(edge, depth));
        _queue.AddToBack(vertex);
    }

    protected override void EncounterVertexAgain(TV vertex, TE edge) { }

    public TV GetParent(TV v) {
        var edge = Objects.RequireNonNull(GetSeenData(v)).Edge;
        return edge == null ? default : graph.GetOppositeVertex(edge, v);
    }

    public TE GetSpanningTreeEdge(TV v) =>
        Objects.RequireNonNull(GetSeenData(v)).Edge;

    public int GetDepth(TV v) => Objects.RequireNonNull(GetSeenData(v)).Depth;


    protected override TV ProvideNextVertex() => _queue.RemoveFromFront();

    public class SearchNodeData {
        public SearchNodeData(TE edge, int depth) {
            Edge = edge;
            Depth = depth;
        }

        public TE Edge { get; }

        public int Depth { get; }
    }
}